Digital coding of graphic information is commonly called for in a wide variety of contexts from facsimile data transmission to computerized photograph analysis and pattern recognition, to computer-aided-design applications. The first step in such digitizing is to scan the document in a controlled fashion, measuring the graphic value of the image at each point. Currently available scanning devices are capable of substantially simultaneously delivering a binary output signal for each of n lines of resolution cells, each cell being approximately 0.01 mm square. Thus a one meter long scan line of an engineering drawing for example, would contain 10.sup.5 such resolution cells; a single square centimeter would contain 10.sup.6 resolution cells.
Where, as indicated above, the digitized information is in the form of raster output data from 0.01 mm resolution cells, a typical 80 character alphabetic line might then be coded as approximately 200 information signals for each 20 cm long scan line, a reduction of 99 percent compared to the 2.times.10.sup.4 bits of raw raster output data. When it is considered that a sheet of A4 paper contains 6.times.10.sup.8 such resolution cells, it can be seen that such a coding is still very cumbersome, requiring over a million information signals to code a single page of bi-tonal writing, scan line by scan line. This inefficiency is addressed in the prior art by a number of techniques which look for broader patterns by correlating the run length compressed data across a second dimension, typically by comparing contiguous adjacent scan line data and coding the difference.
Electronic document deskewing is an essential preprocessing capability necessary to enable further document processing of a digitized paper-based form. The present invention provides a fast and accurate method for detecting skew angle of the form image.
To correct a skewed image requires two processing steps: first, establishing the amount of skew and then deskewing of the image by using skew correction. The skew of a document is usually defined by the orientation of the side boundaries of the document and/or the straight lines contained in the image. Secondly, for a form document, it is predominated by straight lines which are the basic element for constructing a form or tables and the orientation of straight lines which help indicate the status of the form skew. Skew of the form image can be implied when a majority of straight lines deviate from either a horizontal or vertical direction.
To detect the orientation of straight boundaries in the past, a Hough transform was used. A direct application of this transform to a bitmap document for line detection has a major disadvantage. It requires extensive computation to make a histogram in parametric space (.rho.,.THETA.) due to the large number of pixels. This can be prohibitive for practical applications.